import java.util.Deque;
import java.util.LinkedList;

/**
 * 面试题31：栈的压入、弹出序列
 */
public class Offer_31 {
    /**
     * 辅助栈
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int len = pushed.length;
        Deque<Integer> stack = new LinkedList<>();
        int i = 0;
        for (int x : pushed) {
            // 元素按顺序入栈
            stack.push(x);
            // 检查这个数是不是 popped 序列中下一个要 pop 的值，如果是就把它 pop 出来
            while (!stack.isEmpty() && i < len && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        // 也可以写 return stack.isEmpty();
        return i == len;
    }

    public static void main(String[] args) {
        Offer_31 solution = new Offer_31();
        // 测试 1
        int[] pushed = new int[] { 1, 2, 3, 4, 5 };
        int[] popped = new int[] { 4, 5, 3, 2, 1 };
        boolean ans = solution.validateStackSequences(pushed, popped);
        System.out.println(ans);
        // 测试 2
        pushed = new int[] { 1, 2, 3, 4, 5 };
        popped = new int[] { 4, 3, 5, 1, 2 };
        ans = solution.validateStackSequences(pushed, popped);
        System.out.println(ans);
    }
}
